/*
 *https://leetcode.cn/problems/count-numbers-with-unique-digits/
 *2376. 统计特殊整数
 *difficult 吴朝泽 2024.9.20
 *数位DP
 和 lc357 基本一模一样，但是这题的参数就是最大区间的边界，不用求 10 的参数次方
 还有个很大的不同点就是本题的区间不包含 0 ，但是 lc357 可以包含 0，故在统计个数时要记得减掉 0 这个数
*/


class Solution {
public:
    int arr[100];     //存储每一位的数字
    long long dp[1024][1024];   //用于记忆化搜索，存储状态

    //pos 表示当前位数，pre 表示前一位的数，flag 表示填的数字大小是否受到限制，lead判断是否含有前导零
    long long DFS(int pos, int pre, bool flag, bool lead)
    {
        //如果位置为 0 直接返回
        if(pos == 0)  return 1;

        //如果没有限制且前一位数有效，并且 dp[pos][pre] 已经被计算过就直接返回
        if(!flag && pre >= 0 && dp[pos][pre] != -1)  return dp[pos][pre];

        //判断最大的数可以是多少，如果 flag 不成立就是 0-9 都可以，否则当前位的数就是最大数
        int max_num = flag ? arr[pos] : 9;

        long long res = 0;   //计数器
        for(int i = 0; i <= max_num; ++i)
        {
            if(i == 0 && lead)
                res += DFS(pos - 1, i, flag && (i == max_num), true);
            else
            {
                //这里使用位运算检测 i 是否被使用过，将 pre 和 1 << i 相与。
                //如果 pre 中的第 i 位是 1，那么结果就会非零，表示数字 i 已经被使用过
                if(pre & (1 << i))  continue;

                //将当前数字 i 的位添加到 pre 中。这样做是为了在下一层递归中记录数字 i 已被使用
                else res += DFS(pos-1, pre | (1 << i), flag && (i == max_num), lead && (i==0));
            }
        }
        if(!flag) dp[pos][pre] = res;
        return res;
    }

    //记录每个数的每一位，arr数组下标从 1 开始，便于记录
    long long check(long long x)
    {
        int pos = 0;
        while(x)
        {
            arr[++pos] = x % 10;
            x /= 10;
        }
        return DFS(pos, 0, 1, 1) - 1;  //第一个参数表示从最高位开始
    }

    int countSpecialNumbers(int n) 
    {
        memset(arr, 0, sizeof(arr));
        //将 dp 数组初始值赋为 -1 ，第 20 行如果未被计算过那此时 dp[pre][pos] 的值就是 -1
        memset(dp, -1 ,sizeof(dp));   
        return check(n);
    }
};